package 变长滑动窗口2

// 难点判断条件 如何在里面 无需关注少了啥 类型够了就可以验证
// !!优化结构 写的一坨
func minWindow(s string, t string) string {
	n1 := len(s)
	n2 := len(t)
	if n1 < n2 {
		return ""
	}
	need := [128]int{}   // 存储t中每个字符需要的数量
	window := [128]int{} // 存储当前窗口中每个字符的数量
	charType := 0        // t中不同字符的种类数（用于判断窗口是否有效）
	for _, c := range t {
		if need[c] == 0 {
			charType++
		}
		need[c]++
	}
	left, right := 0, 0
	valid := 0
	minLen := n1 + 1
	start := 0
	for right < n1 {
		c := s[right]
		right++
		if need[c] > 0 {
			window[c]++
			if window[c] == need[c] {
				valid++
			}
		}
		// 3. 当窗口有效（valid == charType），尝试左指针收缩窗口，找最小长度
		for valid == charType {
			// 计算当前窗口长度，更新最小子串
			currentLen := right - left
			if currentLen < minLen {
				minLen = currentLen
				start = left // 记录起始位置
			}

			// 左指针指向的字符要移出窗口
			leftC := s[left]
			left++

			// 如果移出的是t中需要的字符，检查是否影响valid
			if need[leftC] > 0 {
				// 如果移出后window中该字符数量不足，valid-1
				if window[leftC] == need[leftC] {
					valid--
				}
				window[leftC]--
			}
		}
	}

	// 4. 检查是否找到有效子串
	if minLen == n1+1 {
		return ""
	}
	return s[start : start+minLen]
}

//func isCovered(cntS, cntT []int) bool {
//    for i := 'A'; i <= 'Z'; i++ {
//        if cntS[i] < cntT[i] {
//            return false
//        }
//    }
//    for i := 'a'; i <= 'z'; i++ {
//        if cntS[i] < cntT[i] {
//            return false
//        }
//    }
//    return true
//}
//
//func minWindow(s, t string) string {
//    var cntS, cntT [128]int
//    for _, c := range t {
//        cntT[c]++
//    }
//
//    ansLeft, ansRight := -1, len(s)
//    left := 0
//    for right, c := range s { // 移动子串右端点
//        cntS[c]++ // 右端点字母移入子串
//        for isCovered(cntS[:], cntT[:]) { // 涵盖
//            if right-left < ansRight-ansLeft { // 找到更短的子串
//                ansLeft, ansRight = left, right // 记录此时的左右端点
//            }
//            cntS[s[left]]-- // 左端点字母移出子串
//            left++
//        }
//    }
//    if ansLeft < 0 {
//        return ""
//    }
//    return s[ansLeft
//作者：灵茶山艾府
//链接：https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
